package varvelworld.algorithm.StringSearching;

/**
 * Created by lzh on 2014/8/3.
 */
public class KMP implements IStringSearching {

    @Override
    public int execute(String src, String word) {
        char[] s = src.toCharArray();
        char[] w = word.toCharArray();
        int[] t = new int[w.length];
        if (t.length > 0) t[0] = 0;
        if (t.length > 1) t[1] = 0;
        //建表算法
        for (int i = 2; i < t.length; i++) {
            if (w[i - 1] == w[t[i - 1]]) {
                t[i] = t[i - 1] + 1;
            } else {
                t[i] = 0;
            }
        }
        int k = 0;
        int i;
        for (i = 0; i - k < s.length - w.length + 1; ) {
            if (s[i] == w[k]) {
                k++;
                if (k == w.length - 1)
                    break;
                i++;
            } else {
                k = t[k];
                i = i + 1 + t[k];
            }
        }
        if (k == w.length - 1)
            return i - k + 1;
        else {
            return -1;
        }
    }
}
